package UnitTest;

/**
 * @Auther: Administrator
 * @Date: 2020/1/5/005 12 10
 * @Description: 深度优先节点切割计算
 */
public class DFSDistributedCal {
    /**
     * 目标答案
     */
    private static int ans;
    /**
     * m 节点个数
     * n
     */
    private static int n, m;

    public static void main(String[] args) {
        int[] arrays = {7,2,5,10,8}; int m = 2;
        int i = splitArray(arrays, m);
        System.out.println(i);
    }

    /**
     * nums 数组
     * i 当前遍历的位置
     * cntSubArrays 子数组和
     * curSum 当前和
     * curMax 当前最大值
     */
    private static void dfs(int[] nums, int i, int cntSubarrays, int curSum, int curMax) {
        if (i == n && cntSubarrays == m) {
            ans = Math.min(ans, curMax);
            return;
        }
        if (i == n) {
            return;
        }
        if (i > 0) {
            dfs(nums, i + 1, cntSubarrays, curSum + nums[i], Math.max(curMax, curSum + nums[i]));
        }
        if (cntSubarrays < m) {
            dfs(nums, i + 1, cntSubarrays + 1, nums[i], Math.max(curMax, nums[i]));
        }
    }

    public static int splitArray(int[] nums, int M) {
        ans = Integer.MAX_VALUE;
        n = nums.length;
        m = M;
        dfs(nums, 0, 0, 0, 0);
        return ans;
    }

}
